package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二叉树中的伪回文路径
 *
 * 给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
 *
 * 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
 * User:Mr.Du
 * Date:2023/11/25
 * Time:14:30
 */
public class PseudoPalindromicPaths {
    public int pseudoPalindromicPaths (TreeNode root) {
        return dfs(root, 0);
    }

    /**
     * 理解为输出二叉树的叶子结点即可，将路径上进行异或操作，左后判断异或结果即可
     * @param root
     * @param tmp
     * @return
     */
    public int dfs(TreeNode root, int tmp){

        if(root == null) {
            return 0;
        }
        tmp ^= (1 << root.val);
        if(root.left == null && root.right == null) {
            return (tmp & (tmp - 1)) == 0 ? 1 : 0;
        }
        return dfs(root.right, tmp) + dfs(root.left, tmp);
    }
}
